package com.jxm.linear;

import org.omg.CORBA.PUBLIC_MEMBER;

import java.util.Iterator;

/**
 * @Author: jxm
 * @Description: 单向链表
 * @Date: 2022/6/10 16:53
 * @Version: 1.0
 */
public class LinkList<T> implements Iterable<T>{
    //记录首结点
    private Node head;
    //记录链表的长度
    private int N;



    private class Node{
        //存储元素
        public T item;
        //指向下一个结点
        public Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    public LinkList(){
        //初始化头结点
        this.head = new Node(null,null);
        //初始化元素个数
        this.N = 0;
    }

    //空置线性表
    public void clear(){
        head.next = null;
        this.N = 0;
    }

    //判断线性表是否为空，是返回true，否返回false
    public boolean isEmpty(){
        return N==0;
    }

    //获取线性表中元素的个数
    public int length(){
        return N;
    }

    //读取并返回线性表中的第i个元素的值
    public T get(int i){
        //通过循环，从头结点开始往后找，依次找i次，就可以找到对应的元素
        Node n = head.next;
        for (int index=0;index<i;index++){
            n = n.next;
        }
        return n.item;

    }

    //往线性表中添加一个元素；
    public void insert(T t){
        //找到当前最后一个结点
        Node n = head;
        while (n.next !=null){
            n = n.next;
        }
        //创建新结点，保存元素t
        Node newNode = new Node(t, null);
        //让当前最后一个结点指向新结点
        n.next = newNode;
        //元素的个数+1
        N++;

    }

    //在指定位置i添加元素t
    public void insert(int i,T t){
        if (i<0||i>=N){
            throw new RuntimeException("位置不合法！");
        }
        //找到i位置的前一个节点
        Node pre = head;
        for(int index=0;index<=i-1;index++){
            pre = pre.next;
        }
        //找到i位置的节点
        Node curr = pre.next;
        //创建新节点，并且新节点需要指向原来i位置的节点
        Node newNode = new Node(t,curr);
        //原来i位置的前一个节点指向新节点即可
        pre.next = newNode;
        //元素的个数+1
        N++;
    }

    //删除并返回线性表中第i个数据元素。
    public T remove(int i){
        if (i<0||i>=N){
            throw new RuntimeException("位置不合法！");
        }
        //获取第i个节点位置的上一个
        Node pre = head;
        for(int index = 0;index<=i-1;index++){
            pre = pre.next;
        }
        //找到第i个位置节点
        Node curr = pre.next;
        //找到第i个位置节点的下一个节点
        Node nextNode = curr.next;
        //当前第i个节点的上一个节点指向当前节点的下个节点
        pre.next = nextNode;
        //元素的个数-1
        N--;
        //放回第i个节点的数据
        return curr.item;

    }

    //返回线性表中首次出现的指定的数据元素的位序号，若不存在，则 返回-1。
    public int indexOf(T t){
        //默认是头节点
        int index = 0;
        //从头节点开始找
        Node node = head;
        while ((node = node.next) != null){
            if(node.item.equals(t)){
                return index;
            }
            index++;
        }
        //方式二：
//        for(int i=0;node.next!=null;i++){
//            if(node.item.equals(t)){
//                return i;
//            }
//        }

        return -1;
    }

    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }

    private class LIterator implements Iterator{
        private Node node;
        public LIterator(){
            this.node = head;
        }

        /**
         * 判断是否还有下一个元素
         * @return
         */
        @Override
        public boolean hasNext() {
            return node.next != null;
        }

        /**
         * 获取下一个元素
         * @return
         */
        @Override
        public Object next() {
            //头结点不存数据
            node = node.next;
            return node.item;
        }
    }

    /**
     * 用来反转整个链表
     */
    public void reverse(){
        //判断当前链表是否为空，如果是空链表，则结束运行，如果不是，则调用重载方法reverse完成反转
        if(isEmpty()) return;
        reverse(head.next);
    }


    //反转指定节点curr,并把反转后的节点返回
    public Node reverse(Node curr){
        //判断退出条件
        if(curr.next == null){
            head.next = curr;
            return curr;
        }
        //递归反转当前节点curr的下一个节点，返回值就是链表反转后，当前节点的上一个节点
        Node pre = reverse(curr.next);
        //让返回的节点的下一个节点变回当前节点curr
        pre.next = curr;
        //把当前节点的下一个节点变为null
        curr.next = null;
        return curr;
    }
}
